//
// Created by yangchao on 2022/4/27.
// 33. 搜索旋转排序数组: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
//

#include <vector>
using namespace std;

class Search {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (target == nums[mid]) return mid;
            if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};


